package greed;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

//https://leetcode.cn/leetbook/read/illustration-of-algorithm/lho7d1/
public class LCR_186文物朝代判断 {
    //辅助哈希表
    class Solution {
        public boolean checkDynasty(int[] places) {
            Set<Integer> set = new HashSet<>();
            int max = 0, min = 20;
            for(int i : places){
                if(i == 0) continue;
                max = Math.max(max,i);
                min = Math.min(min,i);
                if(set.contains(i)) return false;
                else set.add(i);
            }
            return max - min < 5;
        }
    }
    //排序 + 遍历
    class Solution2 {
        public boolean checkDynasty(int[] places) {
            Arrays.sort(places);
            int unknown = 0;
            for(int i=0; i<places.length-1; i++){
                if(places[i] == 0) unknown++;
                else if(places[i] == places[i+1]) return false;
            }
            return places[4] -  places[unknown] < 5;
        }
    }
}
